package org.zhangyp.n02datastructure.n02LinkedList;

/**
 * 自己实现的LinkedList
 * 采用单向链表实现
 *
 * @author zhangyp
 * @date 2024/1/25 8:54
 */
public class MyLinkedList<T> {
    private Node<T> head;
    private int size;

    /**
     * 在末尾追加一个数据
     *
     * @param: data
     **/
    public void add(T data) {
        this.add(this.size, data);
    }

    /**
     * 中间插入一个数据
     *
     * @param: index
     * @param: data
     **/
    public void add(int index, T data) {
        if (index > (this.size)) {
            throw new IndexOutOfBoundsException("无法在此处插入数据");
        }
        Node<T> node = new Node<>(data);
        if (index == 0) {
            node.next = head;
            head = node;
        } else {
            Node<T> cur = head;
            int i = 0;
            while (cur != null) {
                // 在要添加的上一个节点处处理
                if (i == index - 1) {
                    node.next = cur.next;
                    cur.next = node;
                }
                cur = cur.next;
                i++;
            }
        }
        this.size++;
    }

    /**
     * 删除某个位置的数据
     *
     * @param: index
     **/
    public void delete(int index) {
        if (index > (this.size - 1)) {
            throw new IndexOutOfBoundsException("此数据不存在");
        }
        // 删除头部
        if (index == 0) {
            head = head.next;
            this.size--;
        } else {
            Node<T> cur = head;
            int i = 0;
            while (cur != null) {
                //在要删除的上一个节点处处理
                if (i == index - 1) {
                    // 无需判断cur.next是否为null，因为经过第一步的判断，cur.next肯定不为null
                    cur.next = cur.next.next;
                    this.size--;
                }
                cur = cur.next;
                i++;
            }
        }
    }

    /**
     * 获取数据
     *
     * @param: index
     **/
    public T get(int index) {
        if (index > (this.size - 1)) {
            throw new IndexOutOfBoundsException("此数据不存在");
        }
        Node<T> cur = head;
        int i = 0;
        while (cur != null) {
            if (i == index) {
                return cur.value;
            }
            cur = cur.next;
            i++;
        }
        return null;
    }

    public void print() {
        System.out.print("[");
        Node<T> cur = head;
        while (cur != null) {
            System.out.print(cur.value + (cur.next == null ? "" : ","));
            cur = cur.next;
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.add("ee");
        list.print();
        System.out.println("第3个数据为：" + list.get(2));
        list.delete(2);
        list.print();
    }
}
